for _ in range(int(input())):
n, k = map(int, input().split())
s = input()
ans = []
for i in range(k):
c = t = 0
for j in range(i, n, k):
if s[j] == '1':
c += 1
else:
c -= 1
t = min(t, c)
ans += c - t,
print(s.count('1') - max(ans))#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
string s;
cin >> s;
// int pre[n];
vector<int> pre(n, 0);
for (int i = 0; i < n; i++)
{
if (i == 0)
pre[i] = s[i] - '0';
else
pre[i] += pre[i - 1] + (s[i] - '0');
}
vector<int> sum(n, 0);
for (int i = n - 1; i >= 0; i--)
{
int xr = (s[i] - '0') ^ 1;
if (i + k - 1 < n)
{
xr += pre[i + k - 1] - pre[i];
}
else
{
xr += pre[n - 1] - pre[i];
}
if (i + k < n)
{
xr += sum[i + k];
}
int r = pre[n - 1] - pre[i] + (s[i] - '0');
sum[i] = min(r, xr);
}
int cnt = 1e15;
for (int i = 0; i < n; i++)
{
int s = sum[i];
if (i)
s += pre[i - 1];
cnt = min(cnt, s);
}
cout << cnt << endl;
}
// int i = 0, j = n - 1;
// while (i < n && s[i] == '0')
// i++;
// while (j >= 0 && s[j] == '0')
// j--;
// if (j < i)
// {
// cout << "0" << endl;
// continue;
// }
// int total = 0;
// for (int l = i; l <= j; l++)
// {
// if (s[l] == '1')
// {
// total++;
// }
// }
// vector<int> rem(k + 1, 0);
// for (int l = i; l <= j; l++)
// {
// if (s[l] == '1')
// {
// rem[(l - i) % (k)]++;
// }
// }
// int ans = 1e6;
// cout << total << endl;
// cout << (j - i + 1) / k << endl;
// for (int l = 0; l < k; l++)
// {
// cout << rem[l] << " ";
// ans = min(ans, (j - i + 1) / k - rem[l] + total - rem[l]);
// cout << ans << " ";
// }
// cout << ans << endl;
}
1711D - Rain | 534A - Exam |
1472A - Cards for Friends | 315A - Sereja and Bottles |
1697C - awoo's Favorite Problem | 165A - Supercentral Point |
1493A - Anti-knapsack | 1493B - Planet Lapituletti |
747B - Mammoth's Genome Decoding | 1591C - Minimize Distance |
1182B - Plus from Picture | 1674B - Dictionary |
1426C - Increase and Copy | 520C - DNA Alignment |
767A - Snacktower | 1365A - Matrix Game |
714B - Filya and Homework | 31A - Worms Evolution |
1691A - Beat The Odds | 433B - Kuriyama Mirai's Stones |
892A - Greed | 32A - Reconnaissance |
1236D - Alice and the Doll | 1207B - Square Filling |
1676D - X-Sum | 1679A - AvtoBus |
1549A - Gregor and Cryptography | 918C - The Monster |
4B - Before an Exam | 545B - Equidistant String |